import java.util.HashSet;
import java.util.Set;

public class Solution {
//    给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中设置位
//    的个数（也被称为汉明重量）。
//    示例 1：
//    输入：n = 11
//    输出：3
//    解释：输入的二进制串 1011 中，共有 3 个设置位。
//    示例 2：
//    输入：n = 128
//    输出：1
//    解释：输入的二进制串 10000000 中，共有 1 个设置位。
//    示例 3：
//    输入：n = 2147483645
//    输出：30
//    解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n &= (n - 1);
            count++;
        }
        return count;
    }

//    给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
//    示例 1：
//    输入：n = 2
//    输出：[0,1,1]
//    解释：
//            0 --> 0
//            1 --> 1
//            2 --> 10
//    示例 2：
//    输入：n = 5
//    输出：[0,1,1,2,1,2]
//    解释：
//            0 --> 0
//            1 --> 1
//            2 --> 10
//            3 --> 11
//            4 --> 100
//            5 --> 101
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for(int i = 0; i <= n; i++){
            int count = 0;
            int tmp = i;
            while(tmp != 0){
                tmp &= (tmp - 1);
                count++;
            }
            ret[i] = count;
        }
        return ret;
    }
//    两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
//    给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
//    示例 1：
//    输入：x = 1, y = 4
//    输出：2
//    解释：
//            1   (0 0 0 1)
//            4   (0 1 0 0)
//            ↑   ↑
//    上面的箭头指出了对应二进制位不同的位置。
//    示例 2：
//    输入：x = 3, y = 1
//    输出：1
    public int hammingDistance(int x, int y) {
        int count = 0;
        int tmp = x ^ y;
        while(tmp != 0){
            tmp &= (tmp - 1);
            count++;
        }
        return count;
    }
//    给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//    你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
//    示例 1 ：
//    输入：nums = [2,2,1]
//    输出：1
//    示例 2 ：
//    输入：nums = [4,1,2,1,2]
//    输出：4
//    示例 3 ：
//    输入：nums = [1]
//    输出：1
    public int singleNumber1(int[] nums) {
         int ret = 0;
         for(int i = 0; i < nums.length; i++){
             ret ^= nums[i];
         }
         return ret;
    }
    public int singleNumber2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(!set.contains(nums[i])){
                set.add(nums[i]);
            }else{
                set.remove(nums[i]);
            }
        }
        Integer[] arr = new Integer[1];
        return set.toArray(arr)[0];
    }

//    给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
//    你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
//    示例 1：
//    输入：nums = [1,2,1,3,2,5]
//    输出：[3,5]
//    解释：[5, 3] 也是有效的答案。
//    示例 2：
//    输入：nums = [-1,0]
//    输出：[-1,0]
//    示例 3：
//    输入：nums = [0,1]
//    输出：[1,0]
    public int[] singleNumber(int[] nums) {
        int[] ret = new int[2];
        //使用抑或，找到分组的方式
        int groupMethod = 0;
        for(int i = 0; i < nums.length; i++){
            groupMethod ^= nums[i];
        }
        groupMethod &= (-groupMethod);
        //分别抑或求解
        for(int i = 0; i < nums.length; i++){
            if((groupMethod & nums[i]) == 0){
                ret[0] ^= nums[i];
            }else{
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }
}
